package bank;

public class _44IsMatch {
    public static boolean isMatch(String s, String p) {
        //  动态规划
        int sLen = s.length(),pLen = p.length();
        boolean[][] dp = new boolean[sLen+1][pLen+1];
        dp[0][0] = true;
        //  除了dp[0][0]==0之外，第0列的所有元素均为false
        //  因为p为空时无法匹配
        for (int i = 1;i <= pLen;i++){
            //  填充第0行的元素
            //  当s为空串时，只有p全部为'*'才能匹配
            if (p.charAt(i-1) == '*'){
                dp[0][i] = true;
            }else {
                break;
            }
        }
        for (int i = 1;i <= sLen;i++){
            for (int j = 1;j <= pLen;j++){
                if (p.charAt(j-1) == '*'){
                    //  这里是重点！！！
                    //  关于 * 的处理：可以使用，也可以不使用
                    dp[i][j] = dp[i][j-1] || dp[i-1][j];
                }else if (p.charAt(j - 1) == '?' || s.charAt(i - 1) == p.charAt(j - 1)){
                    dp[i][j] = dp[i-1][j-1];
                }
            }
        }
        return dp[sLen][pLen];
    }
}
